package BackTracking;//给你两个 m x n 的二进制矩阵 grid1 和 grid2 ，它们只包含 0 （表示水域）和 1 （表示陆地）。一个 岛屿 是由 四个方向 （水平或者竖
//直）上相邻的 1 组成的区域。任何矩阵以外的区域都视为水域。 
//
// 如果 grid2 的一个岛屿，被 grid1 的一个岛屿 完全 包含，也就是说 grid2 中该岛屿的每一个格子都被 grid1 中同一个岛屿完全包含，那
//么我们称 grid2 中的这个岛屿为 子岛屿 。 
//
// 请你返回 grid2 中 子岛屿 的 数目 。 
//
// 
//
// 示例 1： 
//
// 输入：grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], 
//grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
//输出：3
//解释：如上图所示，左边为 grid1 ，右边为 grid2 。
//grid2 中标红的 1 区域是子岛屿，总共有 3 个子岛屿。
// 
//
// 示例 2： 
//
// 输入：grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]], 
//grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]
//输出：2 
//解释：如上图所示，左边为 grid1 ，右边为 grid2 。
//grid2 中标红的 1 区域是子岛屿，总共有 2 个子岛屿。
// 
//
// 
//
// 提示： 
//
// 
// m == grid1.length == grid2.length 
// n == grid1[i].length == grid2[i].length 
// 1 <= m, n <= 500 
// grid1[i][j] 和 grid2[i][j] 都要么是 0 要么是 1 。 
// 
// Related Topics 深度优先搜索 广度优先搜索 并查集 数组 矩阵 👍 47 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class countSubIslands {
    int rows;
    int cols;
    boolean flag;
    public int countSubIslands(int[][] grid1, int[][] grid2) {
        /**
         只遍历grid2的岛屿，判断岛屿是不是都在 grid1中
         */
        int res = 0; //结果
        rows = grid1.length;
        cols = grid1[0].length;
        for(int i=0;i<rows;i++){
            for(int j=0;j<cols;j++){
                //当前位置是岛屿再进入
                if(grid2[i][j]==1){
                    flag = true;
                    dfs(grid1,grid2,i,j);
                    //如果查找一遍岛屿，没有发现违规，添加结果
                    if(flag){
                        res++;
                    }

                }
            }
        }
        return res;
    }

    private void dfs(int[][] grid1, int[][] grid2, int i, int j){
        //不合法的位置
        if(i<0 || i>=rows || j<0 || j>=cols){
            return;
        }
        if(grid2[i][j]==0){
            return;
        }
        //岛屿2的位置不在岛屿1中，则标记为不满足
        if(grid1[i][j]!=1){
            flag=false;
        }

        grid2[i][j] = 0;
        dfs(grid1,grid2,i+1,j);
        dfs(grid1,grid2,i,j+1);
        dfs(grid1,grid2,i-1,j);
        dfs(grid1,grid2,i,j-1);

    }
}
//leetcode submit region end(Prohibit modification and deletion)
